#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""
"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says.

"The second problem is, given an positive integer N, we define an equation like this:
  N=a[1]+a[2]+a[3]+...+a[m];
  a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
  4 = 4;
  4 = 3 + 1;
  4 = 2 + 2;
  4 = 2 + 1 + 1;
  4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is "not same" in this problem. Now, you do it!"


# NOTE: csdn : https://blog.csdn.net/pmt123456/article/details/52776755
"""

import math


class NumberCombine:
    def __init__(self, target_num):
        self.num = target_num

        self.result_cnt = (self.num + 1) * [0]
        self.result_cnt[0] = 1
        self.tmp_cnt = (self.num + 1) * [0]

    def do_cnt(self):
        for cand_num in range(1, self.num+1):
            # 可能的成员取值

            # 注意 num // cand_num的值是可能取到的(比如4//2), 所以需要+1(闭区间, 右移一位)
            for cnt in range(self.num//cand_num + 1):
                value = cand_num * cnt
                if value > self.num:
                    break

                for result_idx in range(self.num+1):
                    # com_value = value + result_idx
                    com_value = cnt + result_idx
                    if com_value <= self.num:
                        # self.tmp_cnt[com_value] += 1 * self.result_cnt[result_idx]
                        # self.tmp_cnt[com_value] += self.result_cnt[result_idx] / math.factorial(cnt)
                        self.tmp_cnt[com_value] += self.result_cnt[result_idx] / math.factorial(cnt)

                        print(
                            '==cnt ',
                            cnt,
                            ' cand_num ',
                            cand_num,
                            " result_idx ",
                            result_idx,
                            " ",
                            self.tmp_cnt,
                            " ",
                            self.tmp_cnt[com_value],
                            # self.tmp_cnt,
                        )

                    # for i in range(self.num+1):
                    #     f = math.factorial(i)
                    #     self.tmp_cnt[i] = int(self.tmp_cnt[i] * f) / f

            # for i in range(self.num+1):
            #     f = math.factorial(i)
            #     self.tmp_cnt[i] = int(self.tmp_cnt[i] * f) / f

            # 一种cand_num所有可能数量都算完了, 计算新的计数
            self.result_cnt =  self.tmp_cnt
            self.tmp_cnt = (self.num+1) * [0]
            if cand_num == 1:
                print("1 end: results: ", self.result_cnt)

        self.result_cnt[-1] = int(self.result_cnt[-1]) * math.factorial(self.num)


def test():
    n = NumberCombine(4)
    n.do_cnt()
    print(n.result_cnt[-1])
    # assert n.result_cnt[-1] == 5

    # n = NumberCombine(5)
    # n.do_cnt()
    # assert n.result_cnt[-1] == 7

    # n = NumberCombine(6)
    # n.do_cnt()
    # assert n.result_cnt[-1] == 11

    # n = NumberCombine(7)
    # n.do_cnt()
    # assert n.result_cnt[-1] == 15

    # n = NumberCombine(120)
    # n.do_cnt()
    # assert n.result_cnt[-1] == 1844349560

    # n = NumberCombine(130)
    # n.do_cnt()
    # assert n.result_cnt[-1] == 5371315400



def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
